import java.util.Arrays;
import java.util.Iterator;
public class RandomQueue<Item> //implements Iterable<Item>
{
    private Item[] queue; // queue element
    private int N; // The number of Items in the queue
    
    // create an empty random queue
    public RandomQueue() { 
        queue = (Item[]) new Object[2];
        N = 0;
    }
    
    // is it empty?
    public boolean isEmpty() { 
        if (N <= 0) {return true;}
        else {return false;}
    }        
    
    // return the number of elements
    public int size() { 
        return queue.length;
    }
    
    //Used to resize the array
    private void resize(int cap) {
        Item[] tmp = (Item[]) new Object[cap];
        for (int i = 0; i < N; i++) {
            tmp[i] = queue[i];
        }
        queue = tmp;
    }
    
    // add an item
    public void enqueue(Item item) {
        //Resize if necessary
        if (N == queue.length) resize(2*queue.length);
        //Add the Item
        queue[N] = item;
        N++;
    }

    // return (but do not remove) a random item
    public Item sample() { 
        if (isEmpty()) { throw new RuntimeException( "Empty queue" ); } 
        else {
        int rn = StdRandom.uniform(N);
        return queue[rn];
        }
    }
    
    // remove and return a random item
    public Item dequeue() { 
        if (isEmpty()) { throw new RuntimeException( "Empty queue" ); } 
        else {
            //Get a random number
            int rn = StdRandom.uniform(N);
             //Store the the Item represented at the random number
            Item tmp = queue[rn];
            //Store the last Item in the array
            Item last   = queue[N-1];
            //Swap the the last Item to place represented by the random number
            queue[rn] = last;
            //remove the Item, we are gonna return
            queue[N-1] = null;
            N--;
            //Resize if necessary
            if (N > 0 && N == queue.length/4) resize(queue.length/2);
            return tmp;
        }
    }
    
    // return an iterator over the items in random order
    public Iterator<Item> iterator() { 
        return new RandomIterator();
    }
    
    private class RandomIterator implements Iterator<Item> {
        private Item[] notused;
        private int i = 0; // how many Items have we returned so far
        
        public RandomIterator() {
            //Make a copy of the array, so changing wont affect the real array
            notused = Arrays.copyOf(queue, N);
        }
        
        public boolean hasNext() {
            if(i < N) {return true; }
            else {return false;}
        }
        
        public void remove() {}
        
        /**
         * Each time we run Item, we incease i by one, this means that for every time Next is run, we choose a random Item from a smaller and smaller array.
         * All Items allready returned, is placed in the back of the list, to keep track of those.
         */
        public Item next() {
            if(hasNext() ) {
                //Get a random number
                int rn = StdRandom.uniform(N-i);
                //Store the the Item represented at the random number
                Item tmp = notused[rn];
                //Store the last Item in the array
                Item last   = notused[N-1-i];
                //Swap the last Item with the one represented at the randomnumber, so that the number we have return is now the last element
                notused[rn] = last;
                notused[N-i-1] = tmp;
                //increase the number of the returned Items
                i++;
                //Return the random Item
                return tmp; }
            else throw new RuntimeException( "Return all" );
        }
    }
        
  public static void main(String args[])
  {
    // Build a queue containing the Integers 1,2,...,6:
    RandomQueue<Integer> Q= new RandomQueue<Integer>();
    for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!
 
    // Print 30 die rolls to standard output
    StdOut.print("Some die rolls: ");
    for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
    StdOut.println();

    // Let's be more serious: do they really behave like die rolls?
    int[] rolls= new int [10000];
    for (int i = 0; i < 10000; ++i)
      rolls[i] = Q.sample(); // autounboxing! Also cool!
    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
    StdStats.stddev(rolls));
    
     //Let's look at the iterator. First, we make a queue of colours:
//    RandomQueue<Integer> W= new RandomQueue<Integer>();
//    for (int i = 1; i < 10000; ++i) W.enqueue(i); // autoboxing! cool!
//    Iterator H= W.iterator();
//    while (H.hasNext()) StdOut.print(H.next()+" ");
    
    RandomQueue<String> C= new RandomQueue<String>();
    C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

    Iterator I= C.iterator();
    Iterator J= C.iterator();
    
    StdOut.print("Two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.print(I.next()+" ");
    
    StdOut.print("\nEntire second shuffle: ");
    while (J.hasNext()) StdOut.print(J.next()+" ");

    StdOut.print("\nRemaining two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.println(I.next());
  }

}
   
//*** Class skeleton ends